A typical aircraft flight process begins with the filing of a flight plan by an airline or pilot with a civil aviation authority (e.g. the Federal Aviation Authority in the United States). The flight plan generally outlines the route of a flight and includes origination and destination location and times as well as intermediate routing information that defines an airway or flight path. Airways, though having no physical existence, are akin to three-dimensional highways and can be defined with a set of intermediate waypoints. Waypoints are reference locations in physical space used for purposes of navigation and typically include a latitude, longitude and altitude. While navigating a flight plan, the aircraft flies a trajectory that traverses the set of waypoints in a sequenced order in time. Hence, the flight path actually flown by the aircraft is referred to as a four-dimensional trajectory as the trajectory includes three spatial coordinates and one temporal coordinate.
Based on the origination, destination and intermediate waypoints, a flight management system or trajectory predictor predicts the four-dimensional trajectory to be flown by the aircraft. It is contemplated that modifying a four-dimensional trajectory based on aircraft related factors (i.e. speed, fuel, altitude, turbulence, wind, weather, etc.) and common resource availability (i.e. runways, airspace, air traffic control services, etc.) can improve the efficiency of an aircraft or a fleet of aircraft with respect to one or more business metrics (i.e. fuel conserved, passenger throughput, cost, etc.). However, predicting a four-dimensional trajectory is a computationally expensive problem. Thus, while the flight management system or trajectory predictor accurately predict a four-dimensional trajectory, the prediction is a relatively time consuming operation. Therefore, directly searching for an optimal four-dimensional trajectory among a continuum of possible four-dimensional trajectories for a flight is unlikely to be computationally feasible in a real-time or near real-time environment. The problem is exacerbated when searching for optimal trajectories for a fleet of aircraft.